/**
 * Created by L.jp
 * Description:我们可以用 2*1 的小矩形横着或者竖着去覆盖更大的矩形。
 * 请问用 n 个 2*1 的小矩形无重叠地覆盖一个 2*n 的大矩形，从同一个方向看总共有多少种不同的方法？
 * 数据范围：0<=n<=38
 * 进阶：空间复杂度O(1)  ，时间复杂度O(N)
 *
 * 注意：约定 n == 0 时，输出 0
 * User: 86189
 * Date: 2021-12-18
 * Time: 19:34
 */
//题目意思就是这个小矩形的长度是2个单位，宽度是1个单位，题目要求用n个这样的小矩形去覆盖长度为2，宽度为n的矩形可以由多少中覆盖方法
    //当n==1时，有1种方法
    //当n==2时，可以两个小矩形可以横着放也可以竖着放，有2种方法
    //当n==3时，可以由前面两项推得，就是在当n==2的基础上分别加一个竖行，对于n==2时的第二种的竖行加在左边右边算不同的，那么就有三种方法
    //当n==4时，就在n==3的基础上加一竖行就有三种了，在n==2的基础上加两个横着放的就有两种了，
// 在n==2和n==3的基础上加一竖行或者放两个横行这些都是每一种只有固定的放法，所以f(4)=f(3)+f（2）
public class Solution {
    public static  int rectCover(int target) {
        //dp算法
        //状态定义：求覆盖2*n的矩形有多少中方法
        //状态转移方程：dp[i]=dp[i-1]dp[i-2]
        //状态初始化：dp[1]=1,dp[2]=2
        /*
        if(target==0 || target==1 || target==2){
            return target;
        }
        int[] dp=new int[target+1];
        dp[1]=1;
        dp[2]=2;
        for(int i=3;i<=target;i++){
            dp[i]=dp[i-1]+dp[i-2];
        }
        return dp[target];

         */

        //递归优化，其实就是斐波那契数列求解问题
        if(target<=2){
            return target;//小于2时，返回对应的值
        }
        int f1=1;
        int f2=2;
        int f3=target;
        while(target>2){
            f3=f1+f2;
            f1=f2;
            f2=f3;
            target--;//需要计算的次数--
        }
        return f3;
    }

    public static void main(String[] args) {
        System.out.println(rectCover(3));

    }
}
